\documentclass{article}
\usepackage[english]{babel}
\usepackage[letterpaper,top=2cm,bottom=2cm,left=3cm,right=3cm,marginparwidth=1.75cm]{geometry}
\usepackage{xeCJK}
\usepackage{indentfirst}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage[colorlinks=true, allcolors=blue]{hyperref}
\usepackage{listings}
\usepackage{float}
\usepackage[colorlinks=true, allcolors=blue]{hyperref}
\usepackage{xcolor}
\usepackage{subfigure}%并排子图 共享标题 有子标题
\usepackage{array}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{listings}
\graphicspath{images/}
\title{Bellman-Ford算法}
\author{舒开宸 3210103247}
\begin{document}
\maketitle
\lstset{language=C++}
\lstset{breaklines}%
\lstset{
    numbers=left, 
    numberstyle= \tiny, 
    keywordstyle= \color{ blue!70},
    commentstyle= \color{red!50!green!50!blue!50}, 
    frame=shadowbox, % 阴影效果
    rulesepcolor= \color{ red!20!green!20!blue!20} ,
    escapeinside=``, % 英文分号中可写入中文
    xleftmargin=2em, aboveskip=1em,
    framexleftmargin=2em
}
\section{设计思路}
从源点source vertex(第一个顶点)开始，将第一个顶点的priority赋值为0，剩余顶点的priority赋值为无穷大$INT_MAX$。先遍历所有顶点，再遍历所有边。任取两个顶点i,j，如果j的priority的小于i的priority与边E[i][j]的边权，则会进行一次松弛，更新j的priority，并将j的父顶点设为i。父顶点用于判断是否存在负边环并用于输出路径和距离。\\
判断负边环，遍历所有的顶点，相当于任取一个顶点j，如果他的priority小于他的父节点i的priority与便E[j][i]的和，说明存在负边环。输出路径和距离，遍历所有顶点，距离是顶点的priority，路径则回用while循环溯节点的父节点直至source vertex。
\section{测试}
\subsection{正确性测试}
\begin{figure}[hp]
    \centering
    \includegraphics[width=6cm]{images/1.jpg}
    \caption{图}
    \label{fig:my_label}
\end{figure}
源点设置为3
\begin{figure}[hp]
    \centering
    \includegraphics[width=8cm]{images/2.png}
    \caption{存在负边环的输入和输出结果}
    \label{fig:my_label}
\end{figure}
\clearpage
下面将顶点9至顶点5的边权从10改成-10，消去负边环。
\begin{figure}[hp]
    \centering
    \includegraphics[width=12cm]{images/3.png}
    \caption{不存在负边环，输出最短路径}
    \label{fig:my_label}
\end{figure}
\subsection{复杂度测试}
复杂度测试需要去掉存在负边环的验证，验证过程是一阶for循环(对单个源点)，故对总体因为有大量数据的输入，故我设计了密集图的测试，测试代码如下：
\begin{lstlisting}
int main()
{
    GraphMatrix<int> matrix; ///建立一个邻接矩阵
    for(int i=0;i<1000;i++)  ///插入顶点，数值不固定在1000
    {
        matrix.insert(i);
    }
    for(int i=0;i<1000;i++) ///插入边
    {
        for(j=0;j<1000;j++)
        matrix.insert(rand()%5-2,i,j);
    }
    clock_t begin;
    clock_t end;
    begin=clock();
    matrix.BellmanFord();  ///测试算法时间
    end=clock();
    cout<<"the searching process takes "<<(double)(end-begin)/CLOCKS_PER_SEC<<endl;

}
\end{lstlisting}
\clearpage
\subsection{测试结果}
\begin{figure}[hp]
    \centering
    \includegraphics[width=10cm]{images/5.png}
    \caption{$500*500$}
    \label{fig:my_label}
\end{figure}
\begin{figure}[hp]
    \centering
    \includegraphics[width=10cm]{images/8.png}
    \caption{$800*800$}
    \label{fig:my_label}
\end{figure}
\begin{figure}[hp]
    \centering
    \includegraphics[width=10cm]{images/10.png}
    \caption{$1000*1000$}
    \label{fig:my_label}
\end{figure}
\subsection{分析}
由于遍历了所有的顶点，又遍历了所有的边，故复杂度为$O(NE)$,我测试的情况则是有$E=N*N$,故复杂度为$O(N^3)$,其中N表示顶点个数，E表示边个数
\clearpage
\section{内存泄漏检查}
\begin{figure}[hp]
    \centering
    \includegraphics[width=12cm]{images/7.png}
    \caption{Caption}
    \label{fig:my_label}
\end{figure}
\end{document}